package com.arrays.a2;

import java.util.Arrays;

/**04-19
 * 最大子数组金和53
 */
public class MaxSubArray53 {

    /*1 贪心
    若当前指针所指元素之前的和小于0，则丢弃当前元素之前的数列
     */

    public int maxSubArray2(int[] nums) {
        int curSum=nums[0];
        int maxSum=curSum;
        for (int i = 1; i < nums.length; i++) {
            //若当前指针所指向 元素之前 的和 小于0，则丢弃当前元素之前的数列
            curSum=Math.max(nums[i],curSum+nums[i]);
            //将当前值与最大值比较，取最大值
            maxSum=Math.max(curSum,maxSum);
        }
        return maxSum;
    }
    /*2 动态规划：
    若前一个元素大于0，则将其加到当前元素上
     */
    public int maxSubArray(int[] nums) {
        int len=nums.length;
        int[] dp=new int[len];
        dp[0]=nums[0];

        for (int i = 1; i < len; i++) {
            if (dp[i-1]>0){
                dp[i]=dp[i-1]+nums[i];
            }else {
                dp[i]=nums[i];
            }
        }
        int res=dp[0];
        for (int i = 0; i < len; i++) {
            res=Math.max(res,dp[i]);
        }
        return res;
    }

    public int maxSubArray1_2(int[] nums) {
        int pre = 0, maxAns = nums[0];
        for (int x : nums) {
            pre = Math.max(pre + x, x);
            maxAns = Math.max(maxAns, pre);
        }
        return maxAns;
    }

    public class Status{
        public int lSum,rSum,mSum,iSum;
        public Status(int lSum,int rSum,int mSum,int iSum){
            this.lSum=lSum;
            this.rSum=rSum;
            this.mSum=mSum;
            this.iSum=iSum;
        }
    }
    public int maxSubArray3(int[] nums) {
        return getInfo(nums,0,nums.length-1).mSum;

    }

    public Status getInfo(int[] a,int l,int r){
        if (l==r){
            return new Status(a[l],a[l],a[l],a[l]);
        }
        int m=(l+r)>>1;
        Status lSub=getInfo(a,l,m);
        Status rSub=getInfo(a,m+1,r);
        return pushUp(lSub,rSub);
    }

    private Status pushUp(Status l, Status r) {
        int iSum = l.iSum + r.iSum;
        int lSum = Math.max(l.lSum, l.iSum + r.lSum);
        int rSum = Math.max(r.rSum, r.iSum + l.rSum);
        int mSum = Math.max(Math.max(l.mSum, r.mSum), l.rSum + r.lSum);
        return new Status(lSum,rSum,mSum,iSum);


    }


}


